// OptimizerPhase1.cpp

#include "OptimizerPhase1.h"
#include "Scoring.h"
#include "Validation.h"
#include <iostream>
#include <algorithm>
#include <random>
#include <omp.h>
#include <limits>

OptimizationResult OptimizerPhase1::optimizer_random_sampling_bottleneck1(
    const std::vector<int>& initial_schedule,
    const std::vector<long long>& initial_history,
    long long initial_score,
    const Graph& graph,
    const CodeMap& code_map,
    const Options1& options,
    std::mt19937& gen)
{
    std::vector<int> current_schedule = initial_schedule;
    long long best_score = initial_score;
    std::vector<long long> current_history = initial_history;
    int num_nodes = graph.get_num_nodes();
    int iterations_without_improvement = 0;
    
    // 收敛历史记录
    std::vector<long long> convergence_history;
    std::vector<int> improvement_iterations;
    
    // 记录初始分数
    convergence_history.push_back(initial_score);
    improvement_iterations.push_back(0);

    for (int iter = 1; iter <= options.iterations; ++iter) {
        auto max_it = std::max_element(current_history.begin(), current_history.end());
        int peak_idx = static_cast<int>(std::distance(current_history.begin(), max_it)) + 1;
        if (current_history.empty() || *max_it == 0) { peak_idx = num_nodes; }

        std::uniform_int_distribution<> distrib(1, peak_idx);
        int node_idx_to_move = distrib(gen);
        int node_to_move = current_schedule[node_idx_to_move - 1];

        // ���޸�: ������Ч�ƶ���Χ���߼�
        int latest_ancestor_pos = 0;
        int earliest_descendant_pos = num_nodes + 1;

        std::vector<int> node_positions(num_nodes + 1, 0);
        for (size_t i = 0; i < current_schedule.size(); ++i) node_positions[current_schedule[i]] = static_cast<int>(i + 1);

        // ʹ��ֱ��ǰ��(���ڵ�)��ȷ������λ��
        for (int parent_id : graph.get_predecessors(node_to_move)) {
            latest_ancestor_pos = std::max(latest_ancestor_pos, node_positions[parent_id]);
        }

        // ʹ��ֱ�Ӻ��(�ӽڵ�)��ȷ������λ��
        for (int child_id : graph.get_successors(node_to_move)) {
            earliest_descendant_pos = std::min(earliest_descendant_pos, node_positions[child_id]);
        }

        std::vector<int> valid_range;
        for (int i = latest_ancestor_pos + 1; i < earliest_descendant_pos; ++i) {
            if (i != node_idx_to_move) { valid_range.push_back(i); }
        }

        if (valid_range.empty()) {
            iterations_without_improvement++;
            continue;
        }

        std::vector<int> positions_to_evaluate;
        std::shuffle(valid_range.begin(), valid_range.end(), gen);
        if (valid_range.size() > options.batch_size) {
            positions_to_evaluate.assign(valid_range.begin(), valid_range.begin() + options.batch_size);
        }
        else {
            positions_to_evaluate = valid_range;
        }
        int batch_size = static_cast<int>(positions_to_evaluate.size());
        std::vector<std::vector<int>> candidate_schedules(batch_size);
        std::vector<long long> candidate_scores(batch_size, std::numeric_limits<long long>::max());
#pragma omp parallel for
        for (int k = 0; k < batch_size; ++k) {
            int new_pos = positions_to_evaluate[k];
            std::vector<int> temp_schedule = current_schedule;
            temp_schedule.erase(temp_schedule.begin() + node_idx_to_move - 1);
            int adjusted_pos = new_pos > node_idx_to_move ? new_pos - 1 : new_pos;
            temp_schedule.insert(temp_schedule.begin() + adjusted_pos - 1, node_to_move);
            candidate_schedules[k] = temp_schedule;
            candidate_scores[k] = Scoring::calculate_max_vstay(temp_schedule, graph, code_map).first;
        }
        long long best_batch_score = std::numeric_limits<long long>::max();
        int best_batch_idx = -1;
        if (!candidate_scores.empty()) {
            auto min_it_batch = std::min_element(candidate_scores.begin(), candidate_scores.end());
            best_batch_score = *min_it_batch;
            best_batch_idx = static_cast<int>(std::distance(candidate_scores.begin(), min_it_batch));
        }
        if (best_batch_idx != -1 && best_batch_score < best_score) {
            const auto& best_candidate_schedule = candidate_schedules[best_batch_idx];
            if (!best_candidate_schedule.empty() && Validation::is_l0_schedule_valid(best_candidate_schedule, graph, code_map)) {
                current_schedule = best_candidate_schedule;
                best_score = best_batch_score;
                current_history = Scoring::calculate_max_vstay(current_schedule, graph, code_map).second;
                iterations_without_improvement = 0;
                
                // 记录收敛历史
                convergence_history.push_back(best_score);
                improvement_iterations.push_back(iter);
                
                fprintf(stdout, "  阶段一 > 迭代 %d / %d: 发现改进解！新分数为: %lld\n", iter, options.iterations, best_score);
            }
            else {
                iterations_without_improvement++;
            }
        }
        else {
            iterations_without_improvement++;
        }
        if (iterations_without_improvement >= options.patience) {
            fprintf(stdout, "  �׶�һ > ���� %d �ε���δ���ָĽ�����ǰ��ֹ��\n", options.patience);
            break;
        }
    }
    // 返回优化结果和收敛历史
    OptimizationResult result;
    result.schedule = current_schedule;
    result.best_score = best_score;
    result.convergence_history = convergence_history;
    result.improvement_iterations = improvement_iterations;
    
    return result;
}